﻿#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_map>
//#include <functional>
using namespace std;

// 滑动窗口
// 定义双指针
// 进窗口
// 判断
//   出窗口
// 更新结果
class Solution {
public:
    //  将 x 减到 0 的最小操作数
    int minOperations(vector<int>& nums, int x) {
        size_t n = nums.size();
        int sum = 0, ret = -1;
        for (auto a : nums) sum += a;
        int target = sum - x;
        if (target < 0) return -1;
        int tmp = 0;
        for (int left = 0, right = 0; right < n; right++)
        {
            tmp += nums[right]; // 进窗口
            while (tmp > target)     // 判断
                tmp -= nums[left++]; // 出窗口
            if (tmp == target)  // 更新结果
                ret = max(ret, right - left + 1);
        }
        if (ret == -1) return ret;
        else return (int)n - ret;
    }
    // 水果成篮
    int totalFruit(vector<int>& fruits) {
        // 统计窗口内出现了多少种水果
        unordered_map<int, int> hash;
        int ret = 0;
        for (int left = 0, right = 0; right < fruits.size(); right++)
        {
            // 进窗口
            hash[fruits[right]]++;
            // 判断
            while (hash.size() > 2)
            {
                // 出窗口
                hash[fruits[left]]--;
                if (hash[fruits[left]] == 0)
                    hash.erase(fruits[left]);
                left++;
            }
            // 更新结果
            ret = max(ret, right - left + 1);
        }
        return ret;
    }
    // 找到字符串中所有字母异位词
    vector<int> findAnagrams(string s, string p) {
        vector<int> ret;
        unordered_map<int, int> hash1;
        unordered_map<int, int> hash2;
        for (int i = 0; i < p.size(); i++) hash2[p[i]]++;
        for (int left = 0, right = 0; right < s.size(); right++)
        {
            // 进窗口
            hash1[s[right]]++;
            // 判断
            if ((right - left + 1) == p.size())
            {
                if (hash1 == hash2)
                    // 更新结果
                    ret.push_back(left);
                // 出窗口
                if (--hash1[s[left]] == 0)
                    hash1.erase(s[left]);
                left++;
            }
        }
        return ret;
    }
    // 串联所有单词的子串
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        unordered_map<string, int> hash2;
        for (auto& str : words) hash2[str]++;
        int len = words[0].size(), n = words.size();
        for (int i = 0; i < len; i++)
        {
            unordered_map<string, int> hash1;
            for (int left = i, right = i, cnt = 0; right + len <= s.size(); right += len)
            {
                string in = s.substr(right, len);
                hash1[in]++;
                if (hash2.count(in) && hash1[in] <= hash2[in]) cnt++;
                if (right - left + 1 > len * n)
                {
                    string out = s.substr(left, len);
                    if (hash2.count(out) && hash1[out] <= hash2[out]) cnt--;
                    hash1[out]--;
                    left += len;
                }
                if (cnt == n)
                    ret.push_back(left);
            }
        }
        return ret;
    }
    // 最小覆盖子串
    string minWindow(string s, string t) {
        int hash_s[128] = {0};
        int hash_t[128] = {0};
        int kinds = 0;
        for (auto ch : t)
            if (hash_t[ch]++ == 0)
                kinds++;
        int minlen = INT_MAX, begin = -1;
        for (int left = 0, right = 0, cnt = 0; right < s.size(); right++)
        {
            char in = s[right];
            if (++hash_s[in] == hash_t[in])
                cnt++;
            while (cnt == kinds)
            {
                if (right - left + 1 < minlen)
                {
                    minlen = right - left + 1;
                    begin = left;
                }
                char out = s[left++];
                if (hash_s[out]-- == hash_t[out])
                    cnt--;
            }
        }
        if (begin == -1) return "";
        else return s.substr(begin, minlen);
    }
};

void minOperations();

void totalFruit();

void findAnagrams();

void findSubstring();

void minWindow();